package com.onpositive.wikipedialookup;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

import com.onpositive.data.units.Units;
import com.onpositive.units.ParsedValueSequence;

public class AbstractRefsLookUp {

	protected RefMap linksMap;
	protected RefMap captionsMap;
	protected int maxCount = Integer.MIN_VALUE;
	ArrayList<String> buf = new ArrayList<String>();
	StringBuilder builder = new StringBuilder();
	
	
	public AbstractRefsLookUp( HashSet<String> map )
	{
		super() ;
		this.linksMap = new RefMap(map) ;
		constructRedirector();
	}
	
	public AbstractRefsLookUp( HashSet<String> lMap, HashSet<String> cMap )
	{
		super() ;
		this.linksMap = new RefMap(lMap) ;				
		this.captionsMap = new RefMap(cMap) ;
		constructRedirector();
	}

	private void constructRedirector() {
//		try {
//			redirector =  new RedirectsInfo2( "C:/wikistorage/wiki refs/redirectsUTF.txt" );
//		} catch (Exception e) {
//			// TODO Auto-generated catch block
//			e.printStackTrace();
//		}
	}

	public AbstractRefsLookUp() {
		super();
	}
	private static final int linkMarksBarrier = 4;
	private static final int needSpaceMarksBarrier = 12;
	private static final String[] punctuationMarks = { " ", "_", "-", "/", ",", ":", ";", "!", "?", ".", "\"","(",")"/*link appropriate marks till here*/,  ParsedValueSequence.valueSeparator } ;
	private static boolean isPunctuationMark( String str, int off )
	{
		for( String s : punctuationMarks )
			if( str.startsWith( s, off ) )
				return true ;
				
		return false ;
	}
	public String processString(String str, boolean onlyTitles, String docName, String propName)
	{
		
		//str = ".50 BMG .ggg ussr hhhh !ay, carmela! (film) hhh ggg .50 BMG naval -fighter [[fighter]]  aircraft ggg sukhoi okb ggg [[reconnaissance]] [[aircraft]] ##### ggg [[Fighter aircraft|samoletik]] . " ;
		//[[Medium bomber]]#####[[reconnaissance aircraft| Reconnaissance]]#####[[Electronic warfare]]#####[[interceptor aircraft|Interceptor]]
		//A_Study_in_Scarlet_(1933_film)
		//A_Spark._To_Pierce_the_Dark.
		//2009_Seguros_Bolivar_Open_Pereira_-_Singles
		//!Ay,_Carmela!_(film)
		//!Ole_Torme!:_Mel_Torme_Goes_South_of_the_Border_with_Billy_May
		//.50 BMG
		ArrayList<String> words = new ArrayList<String>() ;
		ArrayList<String> primaryLinks = new ArrayList<String>() ;
		ArrayList<Integer> primaryLinksIndeces = new ArrayList<Integer>() ;
		ArrayList<Integer> marks = new ArrayList<Integer>() ;
		
		
		performInitialSplit( str, words, marks, primaryLinks, primaryLinksIndeces ) ;
		
		expandLinks( words, marks, primaryLinks, primaryLinksIndeces ) ;
		
		detectNewlinks( words, marks, primaryLinksIndeces ) ;
		
		String newString = buildNewString( words, marks ) ;		
	
		return newString ;
		//return str ;
	}	

	private static final int MAX_PHRASE_SEARCH_SIZE = 15 ;
	private void detectNewlinks(ArrayList<String> words, ArrayList<Integer> marks, ArrayList<Integer> primaryLinksIndeces )
	{
		
		int blockStart, blockEnd, lowerBound, upperBound ;
		
		for( int i = 0 ; i < primaryLinksIndeces.size() ; i += 2 )
		{
			blockStart = primaryLinksIndeces.get(i) ;
			
			if( blockStart < 0 )
				continue ;
				
			blockEnd = primaryLinksIndeces.get( i+1 ) ;
			
			if( blockStart == blockEnd )
				continue ;
			
			lowerBound = blockStart ;
			upperBound = blockStart+1 ;
				
			extractLinksFromRange( lowerBound, blockEnd, words, marks ) ;

		}
	}	

	private void expandLinks( ArrayList<String> words, ArrayList<Integer> marks, ArrayList<String> primaryLinks, ArrayList<Integer> primaryLinksIndeces )
	{
		
		int lowerBound ;
		
		for( int i = 0 ; i < primaryLinks.size() ;  )
		{
			lowerBound = primaryLinksIndeces.get( i+1 ) ;

			StringWithShift refData = detectRefExpansion( lowerBound, i, words, marks, primaryLinks) ;
			
			builder.delete( 0, builder.length() ) ;			
			if( refData == null ){
				String ref = primaryLinks.get( i);
				String caption = primaryLinks.get( i+1) ;
					
				builder.append( "[[" ) ;
				
				if( ref != null && ref.length() != 0 )
				{
					builder.append(ref );
				
					if( caption != null && caption.length() != 0 ){
						builder.append( "|" ) ;
						builder.append( caption ) ;
					}
				}
				builder.append( "]]" ) ;
				String s = builder.toString() ;
				if( s.length() == 4 )					
					words.set( lowerBound, "" ) ;
				else
					words.set( lowerBound, s ) ;
				
				i +=2 ;
				continue ;
			}
			
			int shift = refData.getShift() ; 			
			//words.set( lowerBound, refData.getValue() ) ;
			
			int refEnd = lowerBound + shift;
			for( int j = lowerBound  ; j < refEnd ; j++ ){
				words.set( j, null ) ;
				marks.set( j, -1 ) ;
			}
			
			words.set( refEnd-1, refData.getValue() ) ;
			marks.set( refEnd-1, 0 ) ;
				
			i += 2 ;			
			for( ; refEnd > primaryLinksIndeces.get(i+1) ; i+=2 )
			{
				primaryLinksIndeces.set( i  , -1 ) ;
				primaryLinksIndeces.set( i+1, -1 ) ;
			}
			
			primaryLinksIndeces.set( i, refEnd ) ;
		}		
	}
	
	ArrayList<StringBuilder> builderList = new ArrayList<StringBuilder>() ;
	ArrayList<ArrayList<Integer>> indexesList = new ArrayList<ArrayList<Integer>>() ;
	
	
	
	private StringWithShift detectRefExpansion( int lowerStartBound, int linkIndex, ArrayList<String> words,
									ArrayList<Integer> marks, ArrayList<String> primaryLinks )
	{
		int s = 1 ;
		prepareBuilders();
		int bound = Math.min( MAX_PHRASE_SEARCH_SIZE, words.size()-lowerStartBound ) ;
		for( int i = 0 ; i < bound ; i++ )
		{
			if( marks.get( lowerStartBound + i) > 0 )
			{
				int _s = s ;
				if( words.get(lowerStartBound + i).equals(" ") )
				{
					if( s >= builderList.size() ){
						for( int j = 0 ; j < s ; j++ ){					
							builderList.add( new StringBuilder( builderList.get(j).toString() )) ;
							indexesList.add( new ArrayList<Integer>( indexesList.get(j) )) ;
						}
					}
					else{
						for( int j = 0 ; j < s ; j++ ){
							builderList.get(s+j).append( builderList.get(j).toString() ) ;
							indexesList.get(s+j).addAll( indexesList.get(j) ) ;
						}
					}
					s *= 2 ;					
				}
				
				for( int j = 0 ; j < _s ; j++ )
					append( "_", j ) ;
				
				continue ;
			}
			
			String str = words.get( lowerStartBound + i ) ;
			if( str != null ){				
				for( int j = 0 ; j < s ; j++ )					
					append(str, j);
				
				continue ;
			}

			//big ???
			String ref = primaryLinks.get( linkIndex ) ;
			String caption = primaryLinks.get( linkIndex+1 ) ;
			linkIndex += 2 ;
				
			if( caption != null && caption.length() != 0 && ref != null && ref.length() != 0 )
			{
				if( s >= builderList.size() ){
					for( int j = 0 ; j < s ; j++ ){					
						builderList.add( new StringBuilder( builderList.get(j).toString() )) ;
						indexesList.add( new ArrayList<Integer>( indexesList.get(j) )) ;
					}
				}
				else{
					for( int j = 0 ; j < s ; j++ ){
						builderList.get(s+j).append( builderList.get(j).toString() ) ;
						indexesList.get(s+j).addAll( indexesList.get(j) ) ;
					}
				}
				for( int j = s ; j < 2*s ; j++ )
					append( caption, j ) ;
		
				for( int j = 0 ; j < s ; j++ )
					append( ref, j ) ;				
				
				s *= 2 ;
			}
			else{				
				if( ref == null )
					ref = caption ;
				
				for( int j = 0 ; j < s ; j++ )
					append( ref, j ) ;
			}
		}		
		
		int maxRefLength = 0 ;
		StringWithShift maxRef = null ;
		for( int j = 0 ; j < s ; j++ )
		{
			StringBuilder bld = builderList.get(j);
			String str = bld.toString().toLowerCase() ;
			ArrayList<Integer> arr = indexesList.get(j) ;
			
			StringWithShift _refData = lookupRef( str, arr, 0 ) ;
			if( _refData != null && _refData.getShift() > maxRefLength )
			{
				maxRefLength = _refData.getShift() ;
				maxRef = _refData ;				
			}
		}
		return maxRef ;

	}

	private void prepareBuilders() {
		for( StringBuilder builder : builderList )
			builder.delete( 0, builder.length() ) ;
				
		for( ArrayList<Integer> arr : indexesList )
			arr.clear() ;				

		if( builderList.size() < 1 )
		{
			builderList.add( new StringBuilder() ) ;
			indexesList.add( new ArrayList<Integer>() ) ;
		}
	}
	
	private StringWithShift detectRefExpansion2( int lowerStartBound, int linkIndex, ArrayList<String> words,
			ArrayList<Integer> marks, ArrayList<String> primaryLinks )
	{		
		for( StringBuilder builder : builderList )
			builder.delete( 0, builder.length() ) ;
				
		for( ArrayList<Integer> arr : indexesList )
			arr.clear() ;				

		int s = 1 ;
		if( builderList.size() < s )
		{
			builderList.add( new StringBuilder() ) ;
			indexesList.add( new ArrayList<Integer>() ) ;
		}
		int currentMark = 0 ;
		int bound = Math.min( MAX_PHRASE_SEARCH_SIZE, words.size()-lowerStartBound ) ;
		for( int i = 0 ; i < bound ; i++ )
		{
			if( currentMark >= linkMarksBarrier )
				break ;
			
			currentMark = marks.get( lowerStartBound + i+1 ) ;
			String str = words.get( lowerStartBound + i ) ;
			if( str != null ){
				for( int j = 0 ; j < s ; j++ )					
					append(str, j);
			}
			else{
				String ref = primaryLinks.get( 2*i + linkIndex ) ;
				String caption = primaryLinks.get( 2*i + linkIndex+1 ) ;
				
				if( caption != null && caption.length() != 0 && ref != null && ref.length() != 0 )
				{
					if( s >= builderList.size() ){
						for( int j = 0 ; j < s ; j++ ){					
							builderList.add( new StringBuilder( builderList.get(j).toString() )) ;
							indexesList.add( new ArrayList<Integer>( indexesList.get(j) )) ;
						}
					}
					else{
						for( int j = 0 ; j < s ; j++ ){
							builderList.get(s+j).append( builderList.get(j).toString() ) ;
							indexesList.get(s+j).addAll( indexesList.get(j) ) ;
						}
					}
					for( int j = s ; j < 2*s ; j++ )
						append( caption, j ) ;
					
					for( int j = 0 ; j < s ; j++ )
						append( ref, j ) ;				
					
					s *= 2 ;
				}
				else{				
					if( ref == null )
						ref = caption ;
					
					for( int j = 0 ; j < s ; j++ )
						append( ref, j ) ;
				}
				
				
			}
			for( int j = 0 ; j < s ; j++ )
				append( "_", j ) ;
		}		
		
		int maxRefLength = 0 ;
		StringWithShift maxRef = null ;
		for( int j = 0 ; j < s ; j++ )
		{
			StringBuilder bld = builderList.get(j);
			String str = bld.substring( 0, bld.length()-1 ) ;
			ArrayList<Integer> arr = indexesList.get(j) ;
			
			StringWithShift _refData = lookupRef( str, arr, 0 ) ;
			if( _refData != null && _refData.getShift() > maxRefLength )
			{
				maxRefLength = _refData.getShift() ;
				maxRef = _refData ;				
			}
		}
		return maxRef ;

	}
	
	

	private void append(String str, int j){
		StringBuilder bld = builderList.get(j);
		ArrayList<Integer> indLst = indexesList.get(j);
		indLst.add( bld.length() ) ;
		bld.append( str ) ;
		indLst.add( bld.length() ) ;
	}
	private void extractLinksFromRange( int lowerBound, int upperBound, ArrayList<String> words, ArrayList<Integer> marks )
	{
		int s = 1 ;
		prepareBuilders();
		
		for( int i = lowerBound ; i < upperBound ; i++ ){
			
			if( marks.get(i) > 0 )
			{
				int _s = s ;
				if( words.get(i).equals(" ") )
				{
					if( s >= builderList.size() ){
						for( int j = 0 ; j < s ; j++ ){					
							builderList.add( new StringBuilder( builderList.get(j).toString() )) ;
							indexesList.add( new ArrayList<Integer>( indexesList.get(j) )) ;
						}
					}
					else{
						for( int j = 0 ; j < s ; j++ ){
							builderList.get(s+j).append( builderList.get(j).toString() ) ;
							indexesList.get(s+j).addAll( indexesList.get(j) ) ;
						}
					}
					s *= 2 ;
					for( int j = _s ; j < s ; j++ )
						append( "", j ) ;
				}
				
				for( int j = 0 ; j < _s ; j++ )
					append( "_", j ) ;
				
				continue ;
			}
			
			String w = words.get(i) ;
			for( int j = 0 ; j < s ; j++ )
				append( w, j ) ;
		}
		
		int range = upperBound - lowerBound ;
		for( int i = 0 ; i < range ; i++ )
		{
			int maxRefLength = 0 ;
			StringWithShift maxRef = null ;
			for( int j = 0 ; j < s ; j++ )
			{
				StringBuilder bld = builderList.get(j);
				String str = bld.toString().toLowerCase() ;
				ArrayList<Integer> arr = indexesList.get(j) ;
				
				StringWithShift _refData = lookupRef( str, arr, i ) ;
				if( _refData != null && _refData.getShift() > maxRefLength )
				{
					maxRefLength = _refData.getShift() ;
					maxRef = _refData ;				
				}
			}
			
			if( maxRef == null )
				continue ;
			
			int shift = maxRef.getShift() ;
			
			for( int j = 0 ; j < shift ; j++ ){
				words.set( lowerBound + i + j, null ) ;
				marks.set( lowerBound + i + j, -1 ) ;
			}
			
			words.set( lowerBound+i+shift-1, maxRef.getValue() ) ;
			marks.set( lowerBound+i+shift-1, 0 ) ;
			
			i += (shift-1) ;
		}
	}
	
	private void extractLinksFromRange3( int lowerBound, int upperBound, ArrayList<String> words, ArrayList<Integer> marks )
	{
		StringBuilder bld = new StringBuilder() ;
		ArrayList<Integer> arr = new ArrayList<Integer>() ;
		
		for( int i = lowerBound ; i < upperBound ; i++ ){
			arr.add( bld.length() ) ;
			bld.append(  marks.get(i) > 0 ? "_" : words.get(i) ) ;
			arr.add( bld.length() ) ;
		}
		
		String str = bld.toString().toLowerCase() ;
		int range = upperBound - lowerBound ;
		for( int i = 0 ; i < range ; i++ )
		{
			StringWithShift refData = lookupRef( str, arr, i ) ;
			if( refData == null )
				continue ;
			
			int shift = refData.getShift() ;
			
			for( int j = 0 ; j < shift ; j++ ){
				words.set( lowerBound + i + j, null ) ;
				marks.set( lowerBound + i + j, -1 ) ;
			}
			
			words.set( lowerBound+i+shift-1, refData.getValue() ) ;
			marks.set( lowerBound+i+shift-1, 0 ) ;
			
			i += (shift-1) ;
		}
	}
	
	private void extractLinksFromRange2( int lowerBound, int upperBound, ArrayList<String> words )
	{
		StringBuilder bld = new StringBuilder() ;
		ArrayList<Integer> arr = new ArrayList<Integer>() ;
		
		for( int i = lowerBound ; i < upperBound ; i++ )
		{
			arr.add( bld.length() ) ;
			bld.append( words.get(i) ) ;
			arr.add( bld.length() ) ;
			bld.append( "_" ) ;			
		}
		bld.delete( bld.length()-1, bld.length() ) ;
		
		String str = bld.toString() ;
		int range = upperBound - lowerBound ;
		for( int i = 0 ; i < range ; i++ )
		{
			StringWithShift refData = lookupRef( str, arr, i ) ;
			if( refData == null )
				continue ;
			
			int shift = refData.getShift() ;
			
			for( int j = 0 ; j < shift ; j++ )
				words.set( lowerBound + i + j, null ) ;
			
			words.set( lowerBound+i+shift-1, refData.getValue() ) ;
			
			i += (shift-1) ;
		}
	}
	
	private StringWithShift lookupRef( String str, ArrayList<Integer> arr, int ind )
	{
		
		int start = 2*ind ;
		int i0 = arr.get(start), i1	;
		String match = null ;
		
		int wordsCount = Math.min( arr.size() >> 1, ind + MAX_PHRASE_SEARCH_SIZE ) - ind ;
		
		for( int end = start + wordsCount * 2 - 1 ; end > start ; end -= 2 )
		{
			i1 = arr.get(end) ;
			String sample = str.substring(i0, i1) ; 
			
			match = linksMap.get( sample ) ;			
			if( match != null )
			{
//				String redirected = redirector.getRedirect(match) ;
//				if( redirected != null)
//					match = redirected ;
			}
			else {
				String m0 = captionsMap.get( sample ) ;
				if(m0 != null )
					match = "|"+ m0 ; 
			}
			
			if( match != null )
				return new StringWithShift( "[["+match+"]]", wordsCount ) ;
				
			wordsCount-- ;
		}
		return null;
	}
	
	
	private String buildNewString(ArrayList<String> words, ArrayList<Integer> marks )
	{
		builder.delete( 0, builder.length() ) ;
		for( String w : words )
		{
			if( w == null )
				continue ;
			
			if( w.startsWith("[[") && !builder.toString().endsWith(" ") ){
				builder.append(" ") ;
				builder.append(w) ;
				continue ;
			}
			if( !w.startsWith(" ") && builder.toString().endsWith("]]") ){
				builder.append(" ") ;
				builder.append(w) ;
				continue ;
			}			
			
			builder.append(w) ;			
		}
		String newString = builder.toString().trim();
		return newString ;
	}
	
	private String buildNewString2(ArrayList<String> words, ArrayList<Integer> marks )
	{
		builder.delete( 0, builder.length() ) ;
		int s = words.size() ;
		Integer mk0 = marks.get(0) ;
		if( mk0 != null )
		{
			builder.append( punctuationMarks[ mk0 ]) ;
			if( mk0 < needSpaceMarksBarrier )
				builder.append(" ") ;			
		}
			
		
		for( int i = 0 ; i < s ; i++ )
		{
			String w = words.get(i);
			if( w == null )
				continue ;
			
			Integer mrk = marks.get(i+1);
			builder.append( w) ;			
			builder.append( punctuationMarks[ mrk ]) ;
			if( mrk < needSpaceMarksBarrier )
				builder.append(" ") ;
		}
		String newString = builder.toString();
		return newString ;
	}
	
	public void  performInitialSplit( String str, ArrayList<String> words, ArrayList<Integer> marks, ArrayList<String> primaryLinks, ArrayList<Integer> primaryLinksIndeces )
	{
		String phrase, fullLinkString ;
		int prev = 0 ;		
		primaryLinksIndeces.add( 0 ) ;
		for( int i = str.indexOf("[[") ; i >= 0 ; i = str.indexOf("[[", prev ) )
		{			
			phrase = str.substring( prev, i ) ;
			prev = str.indexOf("]]",i) ;
			fullLinkString = str.substring( i+2, prev ) ;
			prev += 2 ;
			
			splitPhrase( phrase, words, marks ) ;
			splitLinkString( fullLinkString, primaryLinks ) ;
			
			primaryLinksIndeces.add( words.size() ) ;
			words.add( null ) ;
			marks.add( -1 ) ;
			primaryLinksIndeces.add( words.size() ) ;			
		}
		
		phrase = str.substring( prev, str.length() );
		splitPhrase( phrase, words, marks ) ;
		primaryLinksIndeces.add( words.size() ) ;
	}

	public void  performInitialSplit2( String str, ArrayList<String> words, ArrayList<Integer> marks, ArrayList<String> primaryLinks, ArrayList<Integer> primaryLinksIndeces )
	{
		String phrase, fullLinkString ;
		int[] markData = determineMark( str, 0) ;
		
		int prev = 0 ;
		Integer mk0 = null ;
		if( markData != null ){
			prev = markData[1] ;
			mk0 = markData[0] ;
		}
		marks.add(mk0) ;		
		
		primaryLinksIndeces.add( 0 ) ;
		for( int i = str.indexOf("[[") ; i >= 0 ; i = str.indexOf("[[", prev ) )
		{			
			phrase = str.substring( prev, i ) ;
			prev = str.indexOf("]]",i) ;
			fullLinkString = str.substring( i+2, prev ) ;
			prev += 2 ;
			
			splitPhrase( phrase, words, marks ) ;
			splitLinkString( fullLinkString, primaryLinks ) ;
			
			primaryLinksIndeces.add( words.size() ) ;
			words.add( null ) ;
			primaryLinksIndeces.add( words.size() ) ;
			
			//process punctuation mark following the link
			markData = determineMark( str , prev ) ;
			marks.add( markData[0] ) ;			
			prev += markData[1] ;
		}
		
		phrase = str.substring( prev, str.length() );
		splitPhrase( phrase, words, marks ) ;
		primaryLinksIndeces.add( words.size() ) ;
	}


	private void splitLinkString( String fullLinkString, ArrayList<String> primaryLinks )
	{		
		String linkString, captionString = null ;

		int ind = fullLinkString.indexOf("|") ;
		if( ind < 0 )
			linkString = fullLinkString.toLowerCase() ;
		else{
			linkString = fullLinkString.substring(0, ind).toLowerCase().replace(" ", "_") ;
			captionString = fullLinkString.substring( ind + 1 ).toLowerCase().replace(" ", "_") ;
		}

		primaryLinks.add( linkString ) ;
		primaryLinks.add( captionString ) ;
	}

	private void splitPhrase( String phrase, ArrayList<String> words, ArrayList<Integer> marks )
	{
		int prev = 0, l = phrase.length() ;
		for( int i = prev ; i < l ; i++ )
		{
			StringWithShift markData = indicateMark(phrase,i);
			if( markData == null )
				continue ;
			
			if( prev != i ){
				words.add( phrase.substring(prev,i)) ;
				marks.add(0) ;
			}
			words.add( markData.getValue() ) ;
			marks.add(1) ;
			prev = i + markData.getShift() ;
			i = prev-1 ;
		}
		
		if( prev != l ){
			words.add( phrase.substring(prev,l) ) ;
			marks.add(0) ;
		}
	}
	
	private void splitPhrase2( String phrase, ArrayList<String> words, ArrayList<Integer> marks )
	{
		int[] markData = determineMark(phrase, 0);
		int prev = markData != null ? markData[1] : 0 ;
		for( int i = prev ; i < phrase.length() ;i++ )
		{
			for( ; !isPunctuationMark( phrase, i) && i < phrase.length() ; i++  );
			markData = determineMark( phrase, i) ;
			words.add( phrase.substring( prev, i ).toLowerCase() ) ;
			marks.add( markData[0] ) ;
			i += markData[1] ;
			prev = i ;			
		}
		
	}
	
	private static final int eol = 100500 ; 
	private static int[] determineMark( String str, int off )
	{
		if( off >= str.length() )
			return new int[]{ eol , 0 } ;
		
		int bound = off-1 ;
		boolean isMark ;
		int rank = -1, blockBound = 0 ;

		do {
			bound++ ;
			isMark = false ;
			if( bound >= str.length() )
				continue ;
			
			for( int i = 0 ; i < punctuationMarks.length ; i++ )
			{
				String currenMark = punctuationMarks[i];
				if( !str.startsWith( currenMark, bound ) )
					continue ;
				
				isMark = true ;
				
				int currentBlockBound = bound + currenMark.length();
				blockBound = currentBlockBound > blockBound ? currentBlockBound : blockBound ;
				
				if( i > rank )
					rank = i ;					
			}
			
		} while( isMark ) ;
		
		if ( rank < 0 )
			return null ;
		
		int shift = blockBound - off ;
		return new int[]{ rank, shift }; 
	}
	
	private static StringWithShift indicateMark( String str, int off )
	{
		if( off >= str.length() )
			return null ;
		
		char ch = str.charAt(off) ;
		
		if( str.startsWith( ParsedValueSequence.valueSeparator, off ) )
			return new StringWithShift( ParsedValueSequence.valueSeparator, ParsedValueSequence.valueSeparator.length() ) ;		
		
		if( !Character.isJavaIdentifierPart(ch) || ch == '_' || ch == ' ' )
			return new StringWithShift( ""+ch, 1 ) ;
		
		

		return null ; 
	}
	
		
	static final class StringWithShift
	{		
		private final String value ;
		private final int shift ;
		
		public StringWithShift(String value, int shift)
		{
			this.value = value;
			this.shift = shift;
		}
		
		public String getValue() {
			return value;
		}
		public int getShift() {
			return shift;
		}		
	}
	static final class RefMap implements Map<String,String>{
		
		private HashMap<String,String> storage ;
		
		public RefMap( int initialCapacity )
		{
			storage = new HashMap<String, String>( initialCapacity )	;
		}
		
		public RefMap( HashSet<String> set )
		{
			storage = new HashMap<String, String>() ;
			
			add( "A_Study_in_Scarlet_(1933_film)" );
			add( "A_Spark._To_Pierce_the_Dark." );
			add( "2009_Seguros_Bolivar_Open_Pereira_-_Singles" );
			add( "!Ay,_Carmela!_(film)" );
			add( "!Ole_Torme!:_Mel_Torme_Goes_South_of_the_Border_with_Billy_May" );
			
			
			for( String str : set )
				add( str ) ;
		}
		
		public void add( String _str )
		{
			
			if( _str == null || _str.trim().length() == 0 )
				return ;
			
			String str = _str.trim() ;
			String s = canonize(str);
			s = s.equals(str) ? str : s ;
			storage.put( s, str ) ;
		}

		private String canonize(String _str)
		{
			String str = _str.trim() ;
			StringBuilder builder = new StringBuilder() ; 
			for( int i = 0 ; i < str.length() ; i++ )
			{
				String s ;
				StringWithShift markData = indicateMark(str, i ) ;

				if( markData != null ){
					s = "_" ;
					i += (markData.getShift()-1) ;
				}
				else
					s = ""+str.charAt(i) ;

				builder.append( s ) ;
			}
			return builder.toString().toLowerCase().trim() ;
		}

		private String canonize2(String str)
		{
			StringBuilder builder = new StringBuilder() ; 
			int prev = 0 ;
			for( int i = 0 ; i < str.length() ; )
			{
				int[] markData = determineMark(str, i ) ;
				if( markData == null ){
					i++ ;
					continue ;
				}
				
				builder.append( str.substring( prev, i ) ) ;
				builder.append( "_" ) ;
				i += markData[1] ;
				prev = i ;
			}
			builder.append( str.substring( prev, str.length() ) ) ;
			return builder.toString().toLowerCase().trim() ;
		}

		@Override
		public void clear() {
			storage.clear() ;
		}

		@Override
		public boolean containsKey(Object key) {
			return storage.containsKey(key) ;
		}

		@Override
		public boolean containsValue(Object value) {
			return storage.containsValue(value);
		}

		@Override
		public Set<java.util.Map.Entry<String, String>> entrySet() {
			return storage.entrySet() ;
		}

		@Override
		public String get(Object key) {
			return storage.get( key );
		}

		@Override
		public boolean isEmpty() {
			return storage.isEmpty();
		}

		@Override
		public Set<String> keySet() {
			return storage.keySet();
		}

		@Override
		public String put(String key, String value) {
			return null ; //return storage.put(key, value) ;
		}

		@Override
		public void putAll(Map<? extends String, ? extends String> m) {
			//storage.putAll(m) ;			
		}

		@Override
		public String remove(Object key) {	
			if(  !(key instanceof String) )
				return null;
			
			String str = canonize( (String) key );
			return storage.remove( str ) ;			
		}

		@Override
		public int size() {			
			return storage.size();
		}

		@Override
		public Collection<String> values() {
			return storage.values();
		}

	}
	
	public String processString2(String _str, boolean onlyTitles, String docName, String propName) {

		if( _str.trim().length() == 0 )
			return null ;
		//testing case
		//_str = "[[Phazotron]] [[Zhuk radar#Zhuk-A (Export Designation Zhuk-AE)|Zhuk AE]] [[AESA]] radar (or other members of the [[Zhuk radar]] family)" ;
		//_str = "[[Fiat Aviazione|Fiat]]" ;
		builder.delete(0, builder.length() ) ;
		int prev = 0 ;
		
		for( int i = _str.indexOf("[[") ; i >= 0 ; i = _str.indexOf("[[", prev ) )
		{
			builder.append( _str.substring(prev, i ) );
			prev = _str.indexOf("]]",i) + 2;
		}
		builder.append( _str.substring(prev, _str.length() ) );
		String str = builder.toString() ;
		
		
		String[] split = str.toLowerCase().split("[ .,/]") ;
		buf.clear() ;
		for( String s : split )
		{
			s = s.trim() ;
			if( s.length() != 0 )
				buf.add(s) ;
		}
		
		int maxWordsCount = 5 ;
		
		int s = buf.size() ;
		
		boolean alreadyPrintedTheWholeString = false ; 
		
		LinkedHashSet<String> linkMatches = new LinkedHashSet<String>() ;
		boolean sufficient = false ;
		for( int i = 0 ; i < s ; i++ )
		{
			builder.delete(0, builder.length() ) ;
			
			String initialString = buf.get(i);
			
			if( initialString.length() == 1 )
				continue ;
			
			//here we check acronyms
			String is_tmp = initialString.replace(".","").replace("-","").trim() ;			
			if( is_tmp.length() < 4 )
			{
				boolean allCaps = true ;
				for( int j = 0 ; j < is_tmp.length() ; j++ )
				{
					if( !Character.isUpperCase( is_tmp.charAt(j) ) ){
						allCaps = false ;
						break ; 
					}										
				}
				if( !allCaps )
					continue ;
				
				initialString = is_tmp ;
			}
			
			boolean allNonLetters = true ;
			for( int j = 0 ; j < initialString.length() ; j++ )
				if( Character.isLetter( initialString.charAt(j) ) )
				{
					allNonLetters = false ;
					break ;
				}
			
			if( allNonLetters )
				continue ;
			
			if( onlyTitles && !Character.isUpperCase( initialString.charAt(0) ) )
				continue ;
			
			if( Units.isUnit( initialString ) )
				continue ;
			
			boolean isCaption = false ;
			
			String maxString = null ;
			
			if( linksMap.get( initialString )!= null ){
				maxString = initialString ;
				isCaption = false ;
			}
			else if( captionsMap.get(initialString)!= null )
			{
				maxString = initialString ;
				isCaption = true ;
			}
			
			
			int additionalWordsCount = 0 ;
			builder.append( initialString ) ;
			
			int stepsCount = Math.min( maxWordsCount, s - i ) ;			
			for( int j = 1 ; j < stepsCount ; j++ )
			{
				builder.append("_") ;
				builder.append(buf.get(i+j) ) ;
				String currentString = builder.toString() ;
				if( linksMap.get( currentString ) != null ) {
					maxString = currentString ;
					additionalWordsCount = j ;
					isCaption = false ;
				}
				else if( captionsMap.get( currentString )!= null ) {
					maxString = currentString ;
					additionalWordsCount = j ;
					isCaption = true ;
				}					
			}
			
			i += additionalWordsCount ;
			
			if( maxString != null ){
				maxString = maxString.replace("_", " ") ;
				linkMatches.add( isCaption ? "|"+maxString : maxString ) ;
				
				sufficient = true ;
				if( !alreadyPrintedTheWholeString )
				{
					System.out.print( propName + '\n' + _str ) ;
					System.out.print( "\n" ) ;
					alreadyPrintedTheWholeString = true ;
				}
				System.out.print( i + ": " ) ;
				System.out.print( maxString ) ;
				System.out.print( "\n" ) ;
			}
		}
		if( sufficient ){
			System.out.print( "\n\n" ) ;
			String resultingString = _str ;
			
			
			for( String l : linkMatches )
			{
				builder.delete( 0, builder.length() ) ;
				//l is what we place
				//match is what we search
				boolean isCaption = l.startsWith("|");
				String match =  isCaption ? l.substring(1) : l ;
//				String lUC = Character.toUpperCase(match.charAt(0)) + match.substring(1) ; 
//				if( l.startsWith("|") )
//					lUC = "|" + lUC ;
				
				String lcStr = resultingString.toLowerCase() ;
				int j = 0 ;
				int lgth = lcStr.length();
				for( int i = 0 ; i < lgth ; i++ )
				{
					if( lcStr.startsWith("[[", i ) )
					{
						i = lcStr.indexOf("]]",i+2) ;
						if( i < 0 )
							break ;
						i+= 2 ;
					}					
					if( lcStr.startsWith(match, i) )
					{
						builder.append( resultingString.substring( j, i ) ) ;
						j = i + match.length() ;					
						builder.append("[[") ;
						if( isCaption )
							builder.append("|") ;
						builder.append( resultingString.subSequence(i, j) );
						builder.append("]]") ;					
						i = j ;
					}
				}
				builder.append( resultingString.substring( j, resultingString.length() ) ) ;
				
				resultingString = builder.toString() ;
			}
			return resultingString ;
		}
		
		return null ;
	}

}